import codeJamUtils

def compute_badrand_probability_matrix(N):

    M_nextiter = [[0.0 for _ in range(N)] for _ in range(N)]
    M_previter = [[0.0 for _ in range(N)] for _ in range(N)]
    i = N

    swapProb = 1/N
    noSwapProb = 1 - swapProb

    # working backwards from the last iteration of badrand, we can compute the
    # probability that the item at Source before iteration i (0 indexed) will 
    # end up at Dest. We start with i = N, which represents the state after 
    # badrand has completed all iterations. Since no swaps occur at this point 
    # in badrand, we can initialize to probability 1 where Source = Dest and 0
    # otherwise.
    for index in range(N):
        M_previter[index][index] = 1.0
    
    while i > 0:
        # move "back in time" to the previous iteration
        
        M_nextiter = [M_previter[copyi][:] for copyi in range(N)]
        i -= 1
        for source in range(N):
            # The ith iteration of badrand swaps the ith element with a random element

            if source == i:
                # The ith element before this iteration has an equal chance of ending
                # up at each place in the list after this iteration. Hence we can 
                # compute the probability that this element ends up at dest with the
                # following formula
                p = sum(swapProb * M_nextiter[swap][dest] for swap in range(N))
                for dest in range(N):
                   M_previter[source][dest] = p
            else:
                for dest in range(N):
                    # All of the other elements have a 1/N probability of being moved to 
                    # the ith position, and an 1 - 1/N probability of staying in the same
                    # position.
                    M_previter[source][dest] = (swapProb * M_nextiter[i][dest]) + (noSwapProb * M_nextiter[source][dest])
        
    return M_previter;

def guess_generated_by_badrand(permutation, badrand_probability_matrix):
    N = len(permutation)
    
    # We'll compute the probability of the given permutation being generated by
    # badrand, and compare to 1/n!, the probability of any permutation being 
    # generated by proper rand. In order to keep the numbers in a reasonable range, 
    # we'll incrementatlly multiply by factors of n! so that the final product
    # ends up being multiplied by n!.

    p = 1.0
    for i in range(N):
        p *= badrand_probability_matrix[permutation[i]][i]
        p *= (N+1)

    if p > 1.0:
        return "BAD"
    else:
        return "GOOD"

def _parse_input(inputLines):
    line = 1
    numCases = int(inputLines[0])
    cases = []
    for _ in range(numCases):
        len = inputLines[line]
        line += 1
        permutation = [int(c) for c in str.split(inputLines[line])]
        line += 1
        cases.append(permutation)
    return cases
 
if __name__ == "__main__":
    inputLines = codeJamUtils.get_input_lines("properShuffle.txt")
    cases = _parse_input(inputLines)
    N = len(cases[0])
    badrand_probability_matrix = compute_badrand_probability_matrix(N)
    for i, case in enumerate(cases):
        codeJamUtils.write_output("properShuffle.txt", i+1, guess_generated_by_badrand(case, badrand_probability_matrix))